﻿#define SYMMETRY

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Mindless
{
    /// <summary>
    /// A tree of nodes representing checkers board positions and the move transitions between them.
    /// Highly optimized to reduce memory usage.
    /// </summary>
    class MoveTree
    {
        /// <summary>
        /// Creates a new move tree for the given board.
        /// </summary>
        public MoveTree(Board board)
        {
                // create the nodes of the tree
            this.iRoot = this.ObtainNode(board);
            Debug.Assert(this.nodeMap.Count == this.nodeList.Count);
            Console.WriteLine();
            Console.WriteLine("{0:0,0} nodes created", this.nodeMap.Count);
            Console.WriteLine("{0:0,0} links created", this.linkList.Count);

                // free any unused memory
            this.nodeList.TrimExcess();
            this.linkList.TrimExcess();
            GC.Collect();

                // sort links by parent node, then collect child indexes
            this.linkList.Sort(delegate(Link a, Link b)
            {
                return a.ParentIndex.CompareTo(b.ParentIndex);
            });
            this.childIndexes = new BigArray<int>(this.linkList.Count);
            unsafe
            {
                int iParent = -1;
                for (int iLink = 0; iLink < linkList.Count; ++iLink)
                {
                    Link link = this.linkList[iLink];
                    if (link.ParentIndex != iParent)
                    {
                        if (iLink > 0)
                            this.nodeList.AddressOf(iParent)->ChildIndexEnd = iLink;
                        this.nodeList.AddressOf(link.ParentIndex)->ChildIndexStart = iLink;
                        iParent = link.ParentIndex;
                    }
                    this.childIndexes[iLink] = this.linkList[iLink].ChildIndex;
                }
                this.nodeList.AddressOf(iParent)->ChildIndexEnd = linkList.Count;
            }

                // sort links by child node, then collect parent indexes
            this.linkList.Sort(delegate(Link a, Link b)
            {
                return a.ChildIndex.CompareTo(b.ChildIndex);
            });
            this.parentIndexes = new BigArray<int>(this.linkList.Count);
            unsafe
            {
                int iChild = -1;
                for (int iLink = 0; iLink < linkList.Count; ++iLink)
                {
                    Link link = this.linkList[iLink];
                    if (link.ChildIndex != iChild)
                    {
                        if (iLink > 0)
                            this.nodeList.AddressOf(iChild)->ParentIndexEnd = iLink;
                        this.nodeList.AddressOf(link.ChildIndex)->ParentIndexStart = iLink;
                        iChild = link.ChildIndex;
                    }
                    this.parentIndexes[iLink] = this.linkList[iLink].ParentIndex;
                }
                this.nodeList.AddressOf(iChild)->ParentIndexEnd = linkList.Count;
            }
                // free links, now that we have parent and child indexes collected
            this.linkList = null;
            GC.Collect();
        }

        /// <summary>
        /// The index of the receiver's root node. The starting node of the tree.
        /// </summary>
        public Node Root
        {
            get { return this.nodeList[this.iRoot]; }
        }
        int iRoot;

        /// <summary>
        /// Answers a copy of the node with the given index.
        /// </summary>
        public Node GetNode(int iNode)
        {
            return this.nodeList[iNode];
        }

        /// <summary>
        /// Obtains the node corresponding to the given board, creating it if it cannot be found in the receiver.
        /// </summary>
        int ObtainNode(Board board)
        {
                // increment progress
            this.ticker.Tick();

                // prepare to a look for a corresponding node
            bool found = false;
            int iNode = -1;

#if SYMMETRY
                // try all symmetrical variations of the given board
            foreach (Board variation in board.GetVariations())
            {
                if (found = this.nodeMap.TryGetValue(variation, out iNode))
                    break;
            }
#else
            found = this.nodeMap.TryGetValue(board, out iNode);
#endif
                // couldn't find a node for this board, so make a new subtree for it
            if (!found)
                new Node(board, this, out iNode);

            return iNode;
        }

        /// <summary>
        /// We're expecting to build a large number of nodes and links. The chosen values are exactly what
        /// we need for the 6x6x3 game, in order to make it fit in a 32-bit address space.
        /// </summary>
        const int EXPECTED_NODES = 11061917;
        const int EXPECTED_LINKS = 36548756;

        /// <summary>
        /// Every node that's created goes in this list. In order to reduce memory usage (on 64-bit machines)
        /// and to make garbage collection go faster, we don't point directly to nodes. Instead, we use their
        /// index in this list whenever we have to refer to a node.
        /// </summary>
        NodeList nodeList = new NodeList(EXPECTED_NODES);

        /// <summary>
        /// Lookup a node's index, given the node's board.
        /// </summary>
        IDictionary<Board, int /*index*/> nodeMap = new LinearProbeDictionary<Board, int>(EXPECTED_NODES);

        /// <summary>
        /// A parent/child relationship between two nodes.
        /// </summary>
        struct Link
        {
            /// <summary>
            /// Creates a link between the nodes with the given indexes.
            /// </summary>
            public Link(int iParent, int iChild)
            {
                this.ParentIndex = iParent;
                this.ChildIndex = iChild;
            }
            public int ParentIndex;
            public int ChildIndex;

            public override string ToString()
            {
                return string.Format("parent {0}, child {1}", this.ParentIndex, this.ChildIndex);
            }
        };

        /// <summary>
        /// All links in the tree are stored here as the tree is constructed.
        /// </summary>
        BigList<Link> linkList = new BigList<Link>(EXPECTED_LINKS);

        /// <summary>
        /// Contains indexes of child nodes, sorted by parent node index.
        /// </summary>
        BigArray<int> childIndexes = null;

        /// <summary>
        /// Contains indexes of parent nodes, sorted by child node index.
        /// </summary>
        BigArray<int> parentIndexes = null;

        /// <summary>
        /// Display gadget to track progress.
        /// </summary>
        TreeTicker ticker = new TreeTicker();

        /// <summary>
        /// Registers a newly created node, answering its new unique index.
        /// </summary>
        int RegisterNode(ref Node node)
        {
            int iNode = this.nodeList.Count;
            this.nodeList.Add(node);
            this.nodeMap[node.Board] = iNode;

            return iNode;
        }

        /// <summary>
        /// Registers a new link between the nodes with the given indexes.
        /// </summary>
        void RegisterLink(int iParent, int iChild)
        {
            Link link = new Link(iParent, iChild);
            this.linkList.Add(link);
        }

        /// <summary>
        /// Assigns values to the receiver's nodes and returns the value of the root node:
        /// 
        ///    -1: Loss for current player
        ///     0: Draw
        ///     1: Win for current player
        ///     
        /// Call this after creating a move tree in order to determine who wins the game.
        /// </summary>
        /// <remarks>
        /// Because of the Inverse symmetry, we can't assume that the color of a node is always
        /// opposite to that of its parents and children. Fortunately, it doesn't matter.
        /// </remarks>
        public unsafe int Evaluate()
        {
                // initialize all nodes
                // ... all leaf nodes are initialized to -1, since current player cannot move
                // ... all other nodes are initialized to 0 (unreachable nodes will still have this value after evaluation)
            Queue<int> nodes = new Queue<int>(this.nodeList.Count / 4);
            for (int iNode = 0; iNode < this.nodeList.Count; ++iNode)
            {
                Node* pNode = this.nodeList.AddressOf(iNode);
                if (pNode->IsLeaf)
                {
                    pNode->Value = -1;
                    nodes.Enqueue(iNode);
                }
                else
                    pNode->Value = 0;
            }
                // -1 index is a marker that indicates a complete pass through the queue
            nodes.Enqueue(-1);

                // walk up the tree from the leaf nodes
            bool progress = false;
            int nPass = 0;
            while (true)
            {
                    // look at the next node to process
                int iNode = nodes.Dequeue();

                    // process the end-of-pass marker
                if (iNode == -1)
                {
                        // if nothing happened this pass, we're done
                    if (!progress)
                        break;

                        // prepare for another pass
                    nodes.Enqueue(iNode);
                    progress = false;
                    Console.CursorLeft = 0;
                    Console.Write("Evaluation pass {0}: {1:0,0} nodes to process...", ++nPass, nodes.Count);
                }
                else
                {
                    Node* pNode = this.nodeList.AddressOf(iNode);

                        // queue contains only winners and losers
                    Debug.Assert(Math.Abs(pNode->Value) == 1);

                        // requeue the current node?
                    bool requeue = false;

                    foreach (int iParent in pNode->GetParents(this))
                    {
                        Node* pParent = this.nodeList.AddressOf(iParent);

                            // parent has already been processed?
                        if (pParent->Value != 0)
                        {
                                // if good news for the parent, then the parent cannot be a loser
                            Debug.Assert((pNode->Value == 1) || (pParent->Value == 1));
                            continue;
                        }

                            // process the node's relationship to this parent
                        switch (pNode->Value)
                        {
                                // node is a loser, so parent is a winner
                            case -1:
                            {
                                    // mark parent as a winner and enqueue it
                                pParent->Value = 1;
                                pParent->WinnerIndex = iNode;
                                nodes.Enqueue(iParent);
                                progress = true;
                                break;
                            }

                                // node is a winner, so parent might be a loser
                            case 1:
                            {
                                    // parent is a loser iff all its children have bad news (e.g. are opposite color winners)
                                bool allChildren = true;
                                foreach (int iChild in pParent->GetChildren(this))
                                {
                                    Node* pChild = this.nodeList.AddressOf(iChild);
                                    if (pChild->Value != 1)
                                    {
                                        allChildren = false;
                                        break;
                                    }
                                }
                                if (allChildren)
                                {
                                        // mark parent as a loser and enqueue it
                                    pParent->Value = -1;
                                    nodes.Enqueue(iParent);
                                    progress = true;
                                }
                                else
                                    requeue = true;
                                break;
                            }
                        }
                    }
                        // requeue the current node iff it still might have impact on its parents
                    if (requeue)
                        nodes.Enqueue(iNode);
                }
            }

            return this.nodeList[iRoot].Value;
        }

        /// <summary>
        /// Each node in the move tree represents a single board position. Highly optimized to reduce
        /// memory usage.
        /// </summary>
        public struct Node
        {
            /// <summary>
            /// Creates a new subtree rooted at the given board within the given tree.
            /// </summary>
            public Node(Board board, MoveTree tree, out int iNode)
            {
                this.Board = board;
                this.Value = 0;
                this.WinnerIndex = -1;
                this.ChildIndexStart = this.ChildIndexEnd = this.ParentIndexStart = this.ParentIndexEnd = -1;

                    // register this new node with the tree to avoid duplicates (must occur before obtaining children, to handle cycles)
                iNode = tree.RegisterNode(ref this);

                    // obtain child nodes
                using (tree.ticker.Descend())
                {
                    foreach (Board childBoard in board.GetLegalMoves())
                    {
                        int iChildNode = tree.ObtainNode(childBoard);
                        tree.RegisterLink(iNode, iChildNode);
                    }
                }
            }

            /// <summary>
            /// The receiver's board.
            /// </summary>
            public Board Board;

            /// <summary>
            /// The beginning and end of the range of entries in the tree's childIndexes array that contain
            /// the indexes of this node's children. The end value actually refers to the beginning of the 
            /// next range. For example, if start is 2 and end is 5, then entries 2-4 contain the indexes
            /// of this node's children.
            /// </summary>
            public int ChildIndexStart, ChildIndexEnd;

            /// <summary>
            /// The beginning and end of the range of entries in the tree's parentIndexes array that contain
            /// the indexes of this node's parents. The end value actually refers to the beginning of the 
            /// next range. For example, if start is 2 and end is 5, then entries 2-4 contain the indexes
            /// of this node's parents.
            /// </summary>
            public int ParentIndexStart, ParentIndexEnd;

            /// <summary>
            /// Answers the receiver's child nodes.
            /// </summary>
            public IEnumerable<int> GetChildren(MoveTree tree)
            {
                for (int iLink = this.ChildIndexStart; iLink < this.ChildIndexEnd; ++iLink)
                    yield return tree.childIndexes[iLink];
            }

            /// <summary>
            /// Indicates whether the receiver is a leaf in the tree. This is true iff the node has no
            /// children.
            /// </summary>
            public bool IsLeaf
            {
                get { return this.ChildIndexStart == this.ChildIndexEnd; }
            }

            /// <summary>
            /// Answers the receiver's parent nodes.
            /// </summary>
            public IEnumerable<int> GetParents(MoveTree tree)
            {
                for (int iLink = this.ParentIndexStart; iLink < this.ParentIndexEnd; ++iLink)
                    yield return tree.parentIndexes[iLink];
            }

            /// <summary>
            /// The receiver's value, as determined by its owning tree.
            /// </summary>
            public int Value;

            /// <summary>
            /// If the node is a winner, this will contain the index of the child node guaranteeing
            /// victory for the current player.
            /// </summary>
            public int WinnerIndex;

            /// <summary>
            /// Display string.
            /// </summary>
            public override string ToString()
            {
                return string.Format("\r\n{0}\r\n", this.Board);
            }
        }

        /// <summary>
        /// An array of nodes that also supports pointers. This allows us to modify the nodes in the
        /// array without having to make copies of them.
        /// </summary>
        class NodeArray : BigArray<MoveTree.Node>
        {
            public NodeArray(int size) : base(size)
            {
            }

            public unsafe MoveTree.Node* AddressOf(int iNode)
            {
                MoveTree.Node[] chunk = this.chunks[iNode / CHUNK_SIZE];
                fixed (MoveTree.Node* pChunk = &chunk[0])
                {
                    return pChunk + (iNode % CHUNK_SIZE);
                }
            }
        }

        /// <summary>
        /// A list of nodes that also supports pointers. This allows us to modify the nodes in the
        /// list without having to make copies of them.
        /// </summary>
        class NodeList : BigList<MoveTree.Node>
        {
            public NodeList(int capacity) : base(capacity)
            {
            }

            /// <summary>
            /// A node list is built on a node array.
            /// </summary>
            protected override BigArray<Node> AllocateItems(int nItems)
            {
                return new NodeArray(nItems);
            }

            /// <summary>
            /// Answers a pointer to the node at the given index in the receiver.
            /// </summary>
            public unsafe MoveTree.Node* AddressOf(int index)
            {
                NodeArray array = (NodeArray) this.items;

                return array.AddressOf(index);
            }
        }
    }

    class TreeTicker
    {
        IList<int> trace = new List<int>();

        public TreeTicker()
        {
            this.trace.Add(0);
        }

        public Descent Descend()
        {
            return new Descent(this);
        }

        public void Tick()
        {
            int value = this.trace[this.trace.Count - 1];
            this.trace.RemoveAt(this.trace.Count - 1);
            this.trace.Add(value + 1);

            if (++this.ticker % 10000 == 0)
            {
                Console.CursorLeft = 0;
                Console.Write("{0:0,0} links: {1}", this.ticker, this);
            }
        }
        ulong ticker = 0;

        public override string ToString()
        {
            const int MAX_VALUES = 25;

            System.Text.StringBuilder sb = new System.Text.StringBuilder();
            int nValues = 0;
            foreach (int value in this.trace)
            {
                if (nValues > MAX_VALUES)
                    break;
                if (nValues > 0)
                    sb.AppendFormat(" {0}", value);
                nValues += 1;
            }

            if ((2 * MAX_VALUES) - sb.Length > 0)
                sb.Append(new string('.', (2 * MAX_VALUES) - sb.Length));

            return sb.ToString();
        }

        public class Descent : IDisposable
        {
            public Descent(TreeTicker ticker)
            {
                this.ticker = ticker;
                this.ticker.trace.Add(0);
            }
            TreeTicker ticker;

            public void Dispose()
            {
                this.ticker.trace.RemoveAt(this.ticker.trace.Count - 1);
            }
        }
    }
}
